package com.leetcode.offer.chapter5;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author Dennis Li
 * @date 2020/7/16 9:22
 */
public class FindContinuousSequence_57 {
    public int[][] findContinuousSequence(int target) {
        // 采用等差数列
        int temp = 1;
        // 用栈感觉比列表要更节约空间一些
        Deque<int[]> stack = new LinkedList<>();
        for (int n = 2; temp > 0; n++) {
            // 基本的等差数列式子的代换过程
            temp = target - (n * (n - 1) / 2);
            // 正整数序列，因此temp必须要大于0
            if (temp > 0 && (temp % n) == 0) {
                int[] nums = new int[n];
                nums[0] = temp / n;
                for (int j = 1; j < n; j++)
                    nums[j] = nums[j - 1] + 1;
                // 压栈
                stack.push(nums);
            }
        }
        int len = stack.size();
        int[][] ans = new int[len][];
        // 序列个数从多到少，依次出栈可以满足要求
        for (int i = 0; i < len; i++)
            if (!stack.isEmpty()) ans[i] = stack.pop();
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new FindContinuousSequence_57().findContinuousSequence(9));
    }
}
